1. Field of the Invention
The present invention relates to the field of computer systems, in particular, data retrieval techniques in computer systems. More specifically, the present invention relates to data retrieval from a data storage structure, e.g. a set associative cache.
2. Background
In order to expedite the availability of data and improve the overall system performance, there are many situations where a plurality of data vectors and their corresponding selection vectors are stored in an organized manner in complementary storage structures. Each data vector comprises a plurality of data block tuples, each data block tuple comprising a plurality of data elements. Each selection vector comprises a plurality of corresponding selection tuples. Such storage structures may be found in many general as well as special purpose computers regardless of their architectures. Perhaps the most well known example of such storage structures is a set associative cache. Another example is a multi-bank memory system. A not as well known example is a branch prediction table.
Data is retrieved by accessing a data vector and its corresponding selection vector concurrently from the complementary storage structures based on an access key. A data element is selected from a data block tuple using the access key if the corresponding selection tuple satisfies certain predetermined relationship to the access key. Traditionally, the data block tuple, and therefore the data element, are selected after determining which corresponding selection tuple satisfies the predetermined relationship (i.e. a hit).
FIG. 1 illustrates this traditional method of organizing and accessing data, and its disadvantage, with an exemplary n-ways set associative cache. Shown is a cache array 10 comprising a number of cache lines, e.g. 12, each cache line having n tuples of data block, e.g. 14a-14*. Each data block comprises a number of data elements. Also shown is a complementary cache tag array 16 comprising a number of corresponding tag entries, e.g. 18, each tag entry having n tuples of address tag, e.g. 20a-20*, and associated control information (not shown).
The data blocks stored in a cache line, e.g. 12, and their address tags stored in the corresponding tag entry, e.g. 18, are mad concurrently based on the lower order bits of an accessing address 22 and provided to a selector 26 and a comparator 28 respectively. The address tags, e.g. 20a-20*, are compared by the comparator 28 against the translated or untranslated higher order bits of the accessing address 24 to determine if there is a cache hit. An example of translation is virtual to physical translation. If there is a cache hit, the data block tuple corresponding to the address tag providing the cache hit is selected by the selector 26 based on input provided to the selector 26 by the comparator 28. A data element is then selected from the selected data block tuple based on the translated or untranslated higher order bits of the accessing address 24.
The reading out of the data blocks and address tags from the data and tag arrays, 10 and 16, the comparison performed by the comparator 28 and the selection made by the selector 26, are illustrated in FIG. 1 with reference to the timeline 30. As obvious from the illustration and the above description, the data block and data element selections are made after the address tag comparisons are completed. The desired data block and its data elements, even if they are stored in the cache line, are not used immediately after they have been read out of the cache array.
Thus, the traditional approach has at least one disadvantage in that wait time are incurred even for available desired data. The cumulative wait time is particularly costly if the data storage structure is accessed frequently and provides a high hit rate, for example, a large instruction cache. Therefore, it is desirable if available desired data are used as soon as they are read out of the storing structure or shortly thereafter.
As will be disclosed, the present invention provides a method and apparatus for rapidly retrieving data from data storage structures using prior access predictive annotations, also known as dynamic set prediction, which achieves the objects and desired results described earlier.